package com.hy.dp.stock;

public class BuySaleStock03 {


    /**
     * 123.买卖股票的最佳时机III
     * 力扣题目链接
     *
     * 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
     *
     * 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
     *
     * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
     *
     * 示例 1: 输入：prices = [3,3,5,0,0,3,1,4] 输出：6 解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3。
     *
     * 示例 2： 输入：prices = [1,2,3,4,5] 输出：4 解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4。注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
     *
     * 示例 3： 输入：prices = [7,6,4,3,1] 输出：0 解释：在这个情况下, 没有交易完成, 所以最大利润为0。
     *
     * 示例 4： 输入：prices = [1] 输出：0
     * 思路
     * 这道题目相对 121.买卖股票的最佳时机 和 122.买卖股票的最佳时机II 难了不少。
     *
     * 关键在于至多买卖两次，这意味着可以买卖一次，可以买卖两次，也可以不买卖。
     *
     * 接来下我用动态规划五部曲详细分析一下：
     *
     * 1.确定dp数组以及下标的含义
     * 一天一共就有五个状态，
     * 1.没有操作
     * 2.第一次买入
     * 3.第一次卖出
     * 4.第二次买入
     * 5.第二次卖出
     * dp[i][j]中 i表示第i天，j为 [0 - 4] 五个状态，dp[i][j]表示第i天状态j所剩最大现金。
     *
     * 2.确定递推公式
     * 需要注意：dp[i][1]，表示的是第i天，买入股票的状态，并不是说一定要第i天买入股票，这是很多同学容易陷入的误区。
     *
     * 达到dp[i][1]状态，有两个具体操作：
     *
     * 操作一：第i天买入股票了，那么dp[i][1] = dp[i-1][0] - prices[i]
     * 操作二：第i天没有操作，而是沿用前一天买入的状态，即：dp[i][1] = dp[i - 1][1]
     * 那么dp[i][1]究竟选 dp[i-1][0] - prices[i]，还是dp[i - 1][1]呢？
     *
     * 一定是选最大的，所以 dp[i][1] = max(dp[i-1][0] - prices[i], dp[i - 1][1]);
     *
     * 同理dp[i][2]也有两个操作：
     *
     * 操作一：第i天卖出股票了，那么dp[i][2] = dp[i - 1][1] + prices[i]
     * 操作二：第i天没有操作，沿用前一天卖出股票的状态，即：dp[i][2] = dp[i - 1][2]
     * 所以dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])
     *
     * 同理可推出剩下状态部分：
     *
     * dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
     *
     * dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
     *
     * 3.dp数组如何初始化
     * 第0天没有操作，这个最容易想到，就是0，即：dp[0][0] = 0;
     *
     * 第0天做第一次买入的操作，dp[0][1] = -prices[0];
     *
     * 第0天做第一次卖出的操作，这个初始值应该是多少呢？
     *
     * 首先卖出的操作一定是收获利润，整个股票买卖最差情况也就是没有盈利即全程无操作现金为0，
     *
     * 从递推公式中可以看出每次是取最大值，那么既然是收获利润如果比0还小了就没有必要收获这个利润了。
     *
     * 所以dp[0][2] = 0;
     *
     * 第0天第二次买入操作，初始值应该是多少呢？应该不少同学疑惑，第一次还没买入呢，怎么初始化第二次买入呢？
     *
     * 第二次买入依赖于第一次卖出的状态，其实相当于第0天第一次买入了，第一次卖出了，然后在买入一次（第二次买入），那么现在手头上没有现金，只要买入，现金就做相应的减少。
     *
     * 所以第二次买入操作，初始化为：dp[0][3] = -prices[0];
     *
     * 同理第二次卖出初始化dp[0][4] = 0;
     *
     * 4.确定遍历顺序
     * 从递归公式其实已经可以看出，一定是从前向后遍历，因为dp[i]，依靠dp[i - 1]的数值。
     *
     * 5.举例推导dp数组
     *
     * @param prices
     * @return
     */
    public static int maxProfix(int [] prices){
        // 1.确定dp数组以及下标的含义

        int [][] dp = new int[prices.length][5];
        //2.推导 递推式

        //3.初始化
        //定义 5 种状态:
        //0: 没有操作, 1: 第一次买入, 2: 第一次卖出, 3: 第二次买入, 4: 第二次卖出

        dp[0][1] = -prices[0];
        // 初始化第二次买入的状态是确保 最后结果是最多两次买卖的最大利润
        dp[0][3] = -prices[0];
        //4.循环遍历
        for (int i = 1; i < prices.length; i++) {
            // 没有操作
            dp[i][0] = dp[i - 1][0];
            // 第一次 买入       余额 - 买入价
            dp[i][1] = Math.max(dp[i - 1][1],dp[i - 1][0] - prices[i]);
            // 第一次 卖出       持有(可能为负) + 卖出价
            dp[i][2] = Math.max(dp[i - 1][2],dp[i - 1][1] + prices[i]);
            // 第二次 买入
            dp[i][3] = Math.max(dp[i - 1][3],dp[i - 1][2] - prices[i]);
            // 第二次卖出
            dp[i][4] = Math.max(dp[i - 1][4],dp[i - 1][3] + prices[i]);
        }
        //5.推导结果
        return Math.max(dp[prices.length - 1][4] ,dp[prices.length - 1][2]);
    }

    // 版本二: 空间优化
    public static int maxProfix02(int [] prices){

        if (prices == null || prices.length == 0 ){
            return 0;
        }
        int [] dp = new int[4];
        // 初始化
        // 存储两次交易的状态就行了
        // dp[0]代表第一次交易的买入
        dp[0] = -prices[0];
        dp[1] = 0;
        dp[2] = -prices[0];
        // dp[3]代表第二次交易的卖出
        dp[3] = 0;
        // 循环遍历
        for (int i = 1; i <= prices.length; i++) {
            // 要么保持不变，要么没有就买，有了就卖
            dp[0] = Math.max(dp[0],-prices[i - 1]);
            dp[1] = Math.max(dp[1],dp[0] + prices[i - 1]);
            dp[2] = Math.max(dp[2],dp[1]-prices[i - 1]);
            dp[3] = Math.max(dp[3],dp[2] + prices[i - 1]);
        }
        return dp[3];
    }

    public static void main(String[] args) {
        int [] prices = {3,3,5,0,0,3,1,4};
        //int [] prices = {7,6,4,3,1};

        System.out.println("res: "+ maxProfix(prices));
        System.out.println("res: "+ maxProfix02(prices));
    }
}
